package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         406,
		Discription: "根据身高重新建队",
		Level:       2,
		Labels: map[string]int{
			"多元排序": 1,
			"贪心":   1,
		},
	})
}

// 第一关键字降序，第二关键字升序
// 高个子需要优先确定相对位置，因为后面矮个子放那都不会已经确认相对位置的高个子产生影响，而矮个子的位置受高个子的位置影响，所以身高降序，身高高的优先找位置
// 若身高一样，k更小的需要优先确定位置
// 不可能出现身高和k都一样的，否则无法排列
func ReconstructQueue(people [][]int) [][]int {
	sort.Slice(people, func(a, b int) bool {
		if people[a][0] > people[b][0] {
			return true
		}

		if people[a][0] == people[b][0] && people[a][1] < people[b][1] {
			return true
		}

		return false
	})

	res := make([][]int, len(people))
	for _, p := range people {
		index := p[1]
		//在切片指定索引处插入
		res = append(res[:index], append([][]int{p}, res[index:]...)...)
	}

	//最后保留len(people)长度的切片
	return res[:len(people)]
}
